package com.nanbei.dp;

import java.util.Arrays;

/**
 * @ClassDescription:  钢条切割问题 （动态规划） 给一个固定长度的钢条 如何切割使钢条的价值最大
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/9 16:11
 */
public class CutRodProblem {
    /*
        1 2 3 4   // 代表钢条的长度
        1 5 8 9   // 钢条长度所对应的价值
            0   1   2   3   4
        1       1   11  111 1111
                (1) (2) (3) (4)
        2           11  111 1111
                    2   21  211
                            22
                (1) (5) (6) (10)
        3       1   11  111 1111
                    2   21  211
                        3   22
                            31
                (1) (5) (8) (10)
        4       1   11  111 1111
                    2   21  211
                        3   22
                            31
                            4
                (1) (5) (8) (10)

                if(能切割当前长度){
                    Math.max( 上一次的最大价值 ， 当条当前段高度的价值 + （钢条总长度（列） - 当前钢条长度（行）的价值） )
                }else{
                    // 不能切割到当前的长度
                    保留上一次的价值
                }

     */

    public static void main(String[] args) {
        int[] rod = {1, 5, 8, 9};
        int we = cut(rod,4);
        int we2 = cut2(rod,4);
        System.out.println(we);
    }

    private static int cut(int[] rod, int lon) {
        // 价值的长度是从1 开始的，为了对应所以将行也多添加一行
        // 因为长度为0的时候价值也是0 所以多定义一列
        int[][] dp = new int[rod.length + 1][lon + 1];
        System.out.println(Arrays.deepToString(dp));

        for (int r = 1; r < rod.length+1; r++) {
            for (int j = 1; j < lon+1; j++) {
                if (j >= r){
                    dp[r][j] = Math.max( dp[r-1][j] , rod[r-1] + dp[r][j-r] );
                }else {
                    dp[r][j] = dp[r-1][j];
                }
            }
            System.out.println(Arrays.deepToString(dp));
        }

        return dp[rod.length][lon];
    }


    // 降维
    private static int cut2(int[] rod, int lon) {

        int[] dp = new int[lon + 1];
        for (int r = 1; r < rod.length+1; r++) {
            for (int j = 1; j < lon+1; j++) {
                if (j >= r){
                    dp[j] = Math.max(dp[j] , rod[r-1] + dp[j-r] );
                }
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[lon];
    }


}
